package 算法.查找;

public class 分块查找 {
    public static void main(String[] args) {

        int[] arr={16,5,9,12, 21,18,
                32,23,37,26,45,34,
                50,48,61,52,73,66};

        Block b1=new Block(21,0,5);
        Block b2=new Block(45,6,11);
        Block b3=new Block(73,12,17);

        // 定义数组来管理三个块的对象 索引表
        Block[] blockArr={b1,b2,b3};

        // 定义要查找的元素
        int number=45;

        // 定义方法 传递要查找的元素 数组 索引表
        int index=getIndex(number,arr,blockArr);

        System.out.println("索引是："+index);



    }
    // 定义方法返回索引
    private static int getIndex(int number, int[] arr, Block[] blockArr) {
        // 确定number在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);
        System.out.println(indexBlock);

        if(indexBlock==-1){
            return -1;
        }
        // 确定起始索引和节数索引
        int startIndex=blockArr[indexBlock].getStartIndex();
        int endIndex=blockArr[indexBlock].getEndIndex();
        System.out.println(startIndex);
        System.out.println(endIndex);

        for(int i=startIndex;i<=endIndex;i++){
            if(arr[i]==number){
                System.out.println(i);
                return i;
            }
        }
        return -1;
    }

    // 定义方法 确定number在那一块当中
    public static int findIndexBlock(Block[] blockArr,int number){
        for (int i = 0; i < blockArr.length; i++) {
            if(blockArr[i].getMax()>=number){
                System.out.println(i);
                return i;
            }
        }
        return -1;

    }

}
class Block{
    private int max;
    private int startIndex;
    private int endIndex;

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}
